package ljl.alg.jianzhioffer.round2;

public class _46_translate_num {
    
    /**
     * 一个很直白的解发就是回溯：看每一位要还是不要
     * 分两种情况，去下一位，或和上一位构成一位，最后结果加起来，是吧
     * 我大概有这么个思路，就是不会写
     *
     * 我去？她妹妹？居然独自写出来了，我很欣慰，阿我很欣慰
     *
     * */
    public int translateNum_good_but_not_good_enough(int num) {
        String s = String.valueOf(num);
        count(s, 0, s.length());
        return count;
    }
    int count;
    void count(String num, int pos, int len) {
        if (pos >= len) count++;
        else {
            // 当前这一位独自试试
            count(num, pos + 1, len);
            // 当前这一位和前一位试试
            if (pos > 0) {
                int prev = num.charAt(pos - 1) - '0';
                if (prev != 0 && prev * 10 + num.charAt(pos) - '0' <= 25)
                    count(num, pos + 2, len);
            }
            
            
            // 当前这一位和下一位试试？重了，下一位会判断
            // 也就是只有：独自，或和前一位两种情况是吧
        }
    }
    
    /**
    * 原来这个题在考动态规划
     *
     * 别这么轻描淡写 这个题不简单的，尤其这个边界
     *
    * */
    public int translateNum3(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1, len = s.length();
        for (int i = 2; i <= len; i++) {
            int cur = Integer.parseInt(s.substring(i - 2, i));
            int c = cur >=10 && cur <= 25 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
    
    /**
     * 别嫌麻烦。
     * 从右往左遍历也是可以的
     * 你感觉没啥用，其实这个解法会引出下一个解法
     *
     * */
    public int translateNum2(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1, len = s.length();
        for (int i = len - 2; i >= 0; i--) {
            int cur = Integer.parseInt(s.substring(i, i + 2));
            int c = cur >=10 && cur <= 25 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
    
    /**
     * 终极解法，只需要 o1 额外空间；
     * 上面不也是 o1 吗？
     *
     * 这个应该会更快一点
     * 这个方法不需要 parseInt，直接修改 num
     *
     * 很强啊
     *
     * */
    public int translateNum1(int num) {
        int a = 1, b = 1, x, y = num % 10;
        while (num != 0) {
            num /= 10;
            x = num % 10;
            int cur = x * 10 + y;
            int c = cur >= 10 && cur <= 25 ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
}
